package imooc_math.sort;

import java.util.Arrays;

import resource.SortTestHelper;
//归并排序

public class MergeSort {
	private static void merge(Comparable[] arry,int l,int mid,int r){
		
		//System.out.println("l:"+l+",mid:"+mid+",r:"+r);
		Comparable[] tmp=Arrays.copyOfRange(arry,l,r+1);//tmp数组从索引为0开始，到索引为r结束，共r+1个数/与arry相差l
		int i=l,j=mid+1;//左半部分的 初始索引与右半部分的初始索引--[i,mid]/[mid+1,r]--例：最小的：[0,0]/[1,1]
		for(int k=l;k<=r;k++){//l、r都是索引，l-r都必须被赋值。
			//System.out.println(k);
			if(i>mid){//左半部分赋值结束
				arry[k]=tmp[j-l];
				j++;
			}else if(j>r){//右半部分赋值结束
				arry[k]=tmp[i-l];
				i++;
			}else if(tmp[i-l].compareTo(tmp[j-l])<0){//i的初始值为l，所以说是从tmp数组的0索引开始比较的
				arry[k]=tmp[i-l];
				i++;
			}else{
				//System.out.println("k:"+k+" j:"+j+"	tmp[j-l]:"+tmp[j-l]);
				arry[k]=tmp[j-l];
				j++;
			}
		}
		
		
	}
	private static void sort(Comparable[] arry,int l,int r){//最小的部分是0和1
		if(l>=r){//相差1都可以进行排序
		return;
		}
		int mid=(l+r)/2;//相差为1时mid=l/r，接下来的两个方法调用直接return
		sort(arry,l,mid);
		sort(arry,mid+1,r);
		//优化1--当满足一定条件时，才调用merge方法
		if(arry[mid].compareTo(arry[mid+1])>0){
			merge(arry,l,mid,r);//例：最小的：0 0 1
		}
		
	}
	public static Object[] sort(Comparable[] arry){
		int n=arry.length;
		sort(arry,0,n-1);//左闭右闭，传入的参数是最小的索引值与最大的索引值
		return arry;//在arry数组里进行修改
	}
	public static void main(String[] args) {
		/*Integer[] arry=new  SortTestHelper().generateRandomArray(20, 0, 20);
		System.out.println(Arrays.toString(arry));
		Object[] result=sort(arry);
		//System.out.println(Arrays.toString(result));
		new  SortTestHelper().printArray(result);
		*/
		/*Integer[] arry=new  SortTestHelper().generateRandomArray(20000, 0, 10000);
		Integer[] arry2=new  SortTestHelper().generateRandomArray(20000, 0, 10000);
		System.out.println(arry);
		Integer[] arryCopy=Arrays.copyOf(arry,arry.length);
		SortTestHelper sth=new SortTestHelper();
	
		sth.testSort("imooc_math.MergeSort", arry);
		sth.testSort("imooc_math.InsertionSort", arryCopy);*/
		Integer[] arry=new  SortTestHelper().generateNearlyOrderedArray(50000,5);
		SortTestHelper sth=new SortTestHelper();
		Integer[] arryCopy=Arrays.copyOf(arry,arry.length);
		sth.testSort("imooc_math.InsertionSort", arryCopy);
		sth.testSort("imooc_math.MergeSort", arry);
	}
}
